import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class project {
    public boolean isValidSudoku(char[][] board) {
        int row=board.length;
        int col=board[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                char ch=board[i][j];
                if (ch >= '1' && ch <= '9') {
                    if(find(i,j,board)){
                        return false;
                    }
                }
            }
        }
        return true;
    }
    public boolean find(int x,int y,char[][] board){
        int row=board.length;
        int col=board[0].length;
        for(int i=0;i<row;i++){
            if(board[i][y]==board[x][y]&&i!=x){
                return true;
            }
        }
        for(int i=0;i<col;i++){
            if(board[x][i]==board[x][y]&&i!=y){
                return true;
            }
        }
        int r=(x/3)*3;
        int c=(y/3)*3;
        for(int i=r;i<r+3;i++){
            for(int j=c;j<c+3;j++){
                if((board[i][j]==board[x][y])&&(i!=x&&j!=y)){
                    return true;
                }
            }
        }
        return false;
    }



























    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1=nums1.length;
        int len2=nums2.length;
        int len=len1+len2;
        int index1=0;
        int index2=0;
        int left=-1;
        int right=-1;
        for(int i=0;i<=len/2;i++){
            left=right;
            if(index1<len1&&(index2>=len2||nums1[index1]<nums2[index2])){
                right=nums1[index1++];
            }else{
                right=nums2[index2++];
            }
        }
        if(len%2==0){
            return (left+right)/2.0;
        }
        return right;
    }



















    public int minMutation(String start, String end, String[] bank) {
        LinkedList<Integer> list=new LinkedList<>();
        int len=bank.length;
        for(int i=0;i<len;i++){
            if(compare(start,bank[i])){
                list.add(i);
            }
        }
        boolean[] booleans=new boolean[len];
        int swap=1;
        while (!list.isEmpty()){
            for(int index:list){
                if(bank[index].equals(end)){
                    return swap;
                }
                booleans[index]=true;
            }
            int size=list.size();
            while (size>0){
                int index=list.pop();
                for(int i=0;i<len;i++){
                    if(compare(bank[i],bank[index])&&booleans[i]){
                        list.add(i);
                    }
                }
                size--;
            }
        }
        return -1;
    }

    private boolean compare(String start, String s) {
        int sum=0;
        for(int i=0;i<start.length();i++){
            if(start.charAt(i)!=s.charAt(i)){
                sum++;
            }
        }
        return sum==1;
    }
}
